package com.zx._12_算法.actual.lru;

import java.util.HashMap;
import java.util.Map;

/**
 * @version v1.0
 * @Project: knowledge
 * @Title: LRU_简单实现   最近最少使用算法
 * @Description: https://leetcode-cn.com/problems/lru-cache/
 * @author: zhangxue
 * @date: 2020年5月4日下午3:21:10
 * @company: 未知
 * @Copyright: Copyright (c) 2015
 */
public class LRUCache {

    private Map<Integer, Node> map = null;

    private int capacity;

    private int size;

    // 最新的数据在头部
    private Node top;

    private Node tail;

    public LRUCache(int capacity) {
        this.map = new HashMap<Integer, Node>(capacity);
        this.capacity = capacity;
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);

        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));       // 返回  1
        cache.put(3, 3);                        // 该操作会使得密钥 2 作废
        System.out.println(cache.get(2));       // 返回 -1 (未找到)
        cache.put(4, 4);                        // 该操作会使得密钥 1 作废
        System.out.println(cache.get(1));       // 返回 -1 (未找到)
        System.out.println(cache.get(3));       // 返回  3
        System.out.println(cache.get(4));       // 返回  4
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) {
            return -1;
        }
        int value = node.value;
        moveToHead(node);
        return value;
    }

    public void put(int key, int value) {
        Node node = null;
        Map<Integer, Node> mapper = this.map;

        // 保存map
        // 保存链表，已经存在，只修改value就行，并移动位置到top
        if (mapper.containsKey(key)) {
            node = mapper.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            // 容器满了，淘汰tail,在保存数据
            if (!checkCap()) {
                cheanTail();
            }
            node = new Node(key, value);
            addTop(node);
            size++;
        }
        mapper.put(key, node);
    }

    public void moveToHead(Node node) {
        Node toper = this.top;
        Node tailer = this.tail;

        if (toper == null // 数据没有初始化
                || tailer == null // 数据只有一个
        ) {
            return;
        }

        Node pre = node.pre;
        Node next = node.next;

        if (pre == null) {
            // 已经是第一个了，不用动了
        } else if (next == null) {
            //最后一个
            pre.next = null;
            this.tail = pre;
            node.pre = null;

            toper.pre = node;
            node.next = toper;
            this.top = node;
        } else {
            pre.next = next;
            next.pre = pre;
            node.pre = null;

            toper.pre = node;
            node.next = toper;
            this.top = node;
        }

    }

    // 新增的数据放在top,作为最新的
    public void addTop(Node node) {
        // 初始化链表
        if (top == null || tail == null) {
            this.top = node;
            this.tail = node;
        } else {
            Node toper = this.top;
            toper.pre = node;
            node.next = toper;
            this.top = node;
        }
    }

    public boolean checkCap() {
        return capacity > size;
    }

    public void cheanTail() {
        Node tailer = this.tail;
        map.remove(tailer.key);

        Node pre = tailer.pre;
        if (pre != null) {
            pre.next = null;
        }
        this.tail = pre;
        size--;
    }

    /**
     * @title 双向链表
     */
    public static class Node {

        int key;
        int value;
        Node pre;
        Node next;

        public Node(int key, int value) {
            super();
            this.key = key;
            this.value = value;
        }
    }
}
/*
		运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
		
		获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
		写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。
		当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
		
		
		进阶:
		
		你是否可以在O(1) 时间复杂度内完成这两种操作？
		
		
		
		示例:
		
		LRUCache cache = new LRUCache( 2 );
		
		cache.put(1, 1);
		cache.put(2, 2);
		cache.get(1);       // 返回  1
		cache.put(3, 3);    // 该操作会使得密钥 2 作废
		cache.get(2);       // 返回 -1 (未找到)
		cache.put(4, 4);    // 该操作会使得密钥 1 作废
		cache.get(1);       // 返回 -1 (未找到)
		cache.get(3);       // 返回  3
		cache.get(4);       // 返回  4

*/